/************************************************************************
                                                                     
   Xceed Ultimate ListBox for Silverlight                                                                                                                                            
   Copyright (C) 2010 Xceed Software Inc.    
                                                                     
   This program is provided to you under the terms of the GNU General Public  
   License version 2 as published by the Free Software Foundation. 
        
   This program is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY, without even the implied warranty of 
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License along 
   with this program, if not, write to the Free Software Foundation, Inc., 
   51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.

   This program can be provided to you by Xceed Software Inc. under a
   proprietary commercial license agreement for use in non-Open Source
   projects. Visit Xceed.com to find the commercial edition of 
   Xceed Ultimate ListBox for Silverlight.                                    
                                                                      
 **********************************************************************/

using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.ComponentModel;
using System.Diagnostics;
using System.Linq;
using System.Reflection;
using Xceed.Silverlight.Data.Stats;

namespace Xceed.Silverlight.Data
{
  public sealed class ListDataSourceProvider : SyncDataSourceProvider
  {
    #region Static Fields

    private const int MaximumIndexCount = 3;

    #endregion

    #region Constructor

    public ListDataSourceProvider( IEnumerable dataSource )
    {
      if( dataSource == null )
        throw new ArgumentNullException( "dataSource" );

      m_originalDataSource = dataSource;

      DataSourceCollection dataSourceCollection = new DataSourceCollection( dataSource );
      m_collection = new ListDataItemCollection( dataSourceCollection );
    }

    #endregion

    #region CanSkip Property

    public override bool CanSkip
    {
      get
      {
        return true;
      }
    }

    #endregion

    #region CanFilter Property

    public override bool CanFilter
    {
      get
      {
        return true;
      }
    }

    #endregion

    #region CanJumpToItem Property

    public override bool CanJumpToItem
    {
      get
      {
        return true;
      }
    }

    #endregion

    #region CanJump Property

    public override bool CanJump
    {
      get
      {
        return true;
      }
    }

    #endregion

    #region CanFilterGroup Property

    public override bool CanFilterGroup
    {
      get
      {
        return true;
      }
    }

    #endregion

    #region CanCount Property

    public override bool CanCount
    {
      get
      {
        return true;
      }
    }

    #endregion

    #region CanGroupCount Property

    public override bool CanGroupCount
    {
      get
      {
        return true;
      }
    }

    #endregion

    #region CanCalculateStats Property

    public override bool CanCalculateStats
    {
      get
      {
        return true;
      }
    }

    #endregion

    #region ElementType Property

    protected internal override Type ElementType
    {
      get
      {
        return m_collection.ElementType;
      }
    }

    #endregion

    #region CanFilterPredicate Property

    internal override bool CanFilterPredicate
    {
      get
      {
        return true;
      }
    }

    #endregion

    #region DataSource Property

    internal IEnumerable DataSource
    {
      get
      {
        return m_originalDataSource;
      }
    }

    #endregion

    protected override void Initialize()
    {
      base.Initialize();

      // Listen to collection notifications.
      m_collection.CollectionChanged += new NotifyCollectionChangedEventHandler( this.OnNotifyCollectionChanged );
      m_collection.ItemChanged += new EventHandler<ItemChangedEventArgs>( this.OnNotifyItemChanged );
    }

    protected override IEnumerable<SortDescription> GetPrimaryKeyInfo()
    {
      yield return m_collection.PrimaryKeyInfo.Field;
    }

    protected override CountQueryResult ExecuteCountQuery(
      CountQueryParameters queryParameters )
    {
      // Get the appropriate index for the count query.
      bool reversedOrder;
      ListDataItemIndex index = this.GetIndex(
                                  queryParameters.Sort,
                                  queryParameters.Filter,
                                  true,
                                  out reversedOrder );

      long startInlineCount = index.ItemsCount;
      long endInlineCount = 0;

      // Find out the bounds of the filtered group.
      if( queryParameters.FilterGroup != null )
      {
        IEnumerable<object> jumpValues = ListDataSourceProvider.GetFilterGroupValues( queryParameters.FilterGroup.Values );

        // Get the number of items from the start of the group to the end of the source.
        ListDataItemEnumerable groupStartEnumerable = index.GetDataItems( jumpValues, reversedOrder, false );
        startInlineCount = groupStartEnumerable.InlineCount;

        // Get the number of items from the end of the group to the end of the source.
        ListDataItemEnumerable groupEndEnumerable = index.GetDataItems( jumpValues, reversedOrder, true );
        endInlineCount = groupEndEnumerable.InlineCount;
      }

      // Adjust the boundaries according to the desired starting position.
      if( queryParameters.Jump != null )
      {
        JumpRequest jumpRequest = queryParameters.Jump;
        JumpStartPosition startPosition = jumpRequest.StartPosition;
        bool includeStartingItem = ( startPosition == JumpStartPosition.Before );
        IEnumerable<object> jumpValues = ListDataSourceProvider.GetJumpValues( jumpRequest.Values );

        ListDataItemEnumerable enumerable = index.GetDataItems( jumpValues, reversedOrder, !includeStartingItem );
        int inlineCount = enumerable.InlineCount;

        if( inlineCount > endInlineCount )
        {
          startInlineCount = Math.Min( inlineCount, startInlineCount );
        }
        // The desired starting position is after the desired data range.
        else
        {
          startInlineCount = endInlineCount;
        }
      }

      long itemsCount = startInlineCount - endInlineCount;
      Debug.Assert( itemsCount >= 0 );

      return new CountQueryResult( itemsCount );
    }

    protected override DataQueryResult ExecuteDataQuery(
      DataQueryParameters queryParameters )
    {
      SortRequest sortRequest = queryParameters.Sort;
      IEnumerable<SortDescription> sortOrder;

      if( sortRequest == null )
      {
        sortOrder = this.PrimaryKeyInfo;
        sortRequest = new SortRequest( sortOrder );
      }
      else
      {
        sortOrder = sortRequest.SortDescriptions;
      }

      // Get the appropriate index for the data query.
      bool reversedOrder;
      ListDataItemIndex index = this.GetIndex(
                                  sortRequest,
                                  queryParameters.Filter,
                                  false,
                                  out reversedOrder );

      // Get an enumerable that enumerates the items from the desired starting position.
      ListDataItemEnumerable enumerable = this.GetDataItems(
                                            queryParameters,
                                            index,
                                            sortOrder,
                                            reversedOrder );
      long inlineCount = enumerable.InlineCount;
      long totalCount = enumerable.TotalCount;

      // Skip and take only the desired items.
      IEnumerable<RawDataItem> dataItems = enumerable;
      dataItems = ListDataSourceProvider.Skip( dataItems, queryParameters.Skip );
      dataItems = ListDataSourceProvider.Take( dataItems, queryParameters.Take );

      return new DataQueryResult( dataItems, inlineCount, totalCount );
    }

    protected override GroupCountQueryResult ExecuteGroupCountQuery(
      GroupCountQueryParameters queryParameters )
    {
      // There is no group count to return since there is no grouping at all.
      if( ( queryParameters.Sort == null ) || ( queryParameters.Sort.SortDescriptions.Count <= 0 ) )
        return new GroupCountQueryResult( Enumerable.Empty<long>() );

      // Get the appropriate index for the group count query.
      bool reversedOrder;
      ListDataItemIndex index = this.GetIndex(
                                  queryParameters.Sort,
                                  queryParameters.Filter,
                                  true,
                                  out reversedOrder );

      IEnumerable<long> groupCount = this.GetGroupCount(
                                       queryParameters.Jump,
                                       queryParameters.FilterGroup,
                                       index,
                                       queryParameters.Sort.SortDescriptions.Count,
                                       reversedOrder );

      return new GroupCountQueryResult( groupCount );
    }

    protected override StatQueryResult ExecuteStatQuery(
      StatQueryParameters queryParameters )
    {
      Debug.Assert( ( queryParameters.Function != null )
                 && ( queryParameters.Function.StatFunction != null ) );

      StatFunction statFunction = queryParameters.Function.StatFunction;
      StatResult statResult;

      // Find out if we may use the count query to give us the result quicker.
      CountFunction countFunction = statFunction as CountFunction;
      if( ( countFunction != null ) && ( countFunction.IncludeNullValues ) )
      {
        CountQueryResult countQueryResult = this.ExecuteCountQuery(
                                              new CountQueryParameters(
                                                queryParameters.Sort,
                                                queryParameters.Filter,
                                                null,
                                                queryParameters.FilterGroup ) );

        if( countQueryResult != null )
        {
          try
          {
            statResult = new StatResult( countQueryResult.Count );
            countFunction.AccumulateChildResult( statResult );
          }
          catch( Exception e )
          {
            statResult = new StatResult( e );
          }

          return new StatQueryResult( statResult );
        }
      }

      // Get the appropriate index for the stat query.
      bool reversedOrder;
      ListDataItemIndex index = this.GetIndex(
                                  queryParameters.Sort,
                                  queryParameters.Filter,
                                  true,
                                  out reversedOrder );

      // Retrieve the values of the groups to keep.
      IList<object> filterGroupValues = null;
      if( queryParameters.FilterGroup != null )
      {
        filterGroupValues = ListDataSourceProvider.GetFilterGroupValues( queryParameters.FilterGroup.Values ).ToList();
      }

      // Check out if the StatFunction has already been calculated earlier.
      statResult = index.GetStatValue( statFunction, filterGroupValues );

      // No value was found for the StatFunction.
      if( statResult == null )
      {
        ListDataItemEnumerable enumerable;
        long itemsCount;

        if( filterGroupValues != null )
        {
          enumerable = index.GetDataItems( filterGroupValues, reversedOrder, false );

          // Find out the number of items that are in the desired range.
          CountQueryResult countQueryResult = this.ExecuteCountQuery(
                                                new CountQueryParameters(
                                                  queryParameters.Sort,
                                                  queryParameters.Filter,
                                                  null,
                                                  queryParameters.FilterGroup ) );

          itemsCount = countQueryResult.Count;
        }
        else
        {
          enumerable = index.GetDataItems( reversedOrder );
          itemsCount = enumerable.TotalCount;
        }

        // Calculate the StatFunction.
        statResult = ListDataSourceProvider.GetStatResult( statFunction, enumerable, itemsCount );

        // Keep the StatResult to reduce the calculation time next time.
        index.SetStatValue( statFunction, filterGroupValues, statResult );
      }

      return new StatQueryResult( statResult );
    }

    protected override IEnumerable<Type> GetSupportedStatFunctions( Type dataType )
    {
      if( dataType == null )
        yield break;

      yield return typeof( StatFunction );
    }

    protected override void OnInvalidateData()
    {
      m_collection.Reset();
    }

    protected override void OnInvalidateDataObjects( IEnumerable<ItemChangedDescription> itemsChanged )
    {
      this.OnItemsChanged( itemsChanged );
    }

    protected override void OnDataObjectsAdded( IEnumerable<object> itemsAdded )
    {
      m_collection.Synchronize();
    }

    protected override void OnDataObjectsRemoved( IEnumerable<object> itemsRemoved )
    {
      m_collection.Synchronize();
    }

    internal override bool IsStatFunctionSupportedNatively( StatFunction statFunction )
    {
      if( ( statFunction == null ) || ( !statFunction.RequiresAccumulation ) )
        return false;

      StatFunction[] prerequisiteFunctions = statFunction.PrerequisiteFunctions;

      return ( prerequisiteFunctions == null )
          || ( prerequisiteFunctions.Length <= 0 );
    }

    internal override bool FindElementMemberType( string memberName, out Type type )
    {
      ListDataItemPrimaryKeyDescription primaryKeyInfo = m_collection.PrimaryKeyInfo;
      if( memberName == primaryKeyInfo.Field.PropertyName )
      {
        type = primaryKeyInfo.Type;
        return true;
      }

      return base.FindElementMemberType( memberName, out type );
    }

    internal override bool TryWrapDataObject( object item, out RawDataItem dataItem )
    {
      dataItem = item as RawDataItem;
      if( dataItem != null )
        return true;

      return this.TryGetItem( item, out dataItem );
    }

    internal override bool TryUnwrapLayer( RawDataItem dataItem, out object item )
    {
      item = dataItem;

      return ( dataItem != null );
    }

    private ListDataItemEnumerable GetDataItems(
      DataQueryParameters queryParameters,
      ListDataItemIndex index,
      IEnumerable<SortDescription> sortOrder,
      bool reverseOrder )
    {
      if( index == null )
        throw new ArgumentNullException( "index" );

      if( sortOrder == null )
        throw new ArgumentNullException( "sortOrder" );

      // Set the query parameters to start at a precise item.
      ListDataItemEnumerable enumerable;
      if( queryParameters.ItemJump != null )
      {
        RawDataItem startingItem = queryParameters.ItemJump.Item as RawDataItem;
        if( startingItem == null )
          throw new DataInternalException( "An attempt was made to jump to an unknown item." );

        IEnumerable<object> memberValues = ListDataSourceProvider.GetMemberValues( startingItem, sortOrder );

        enumerable = index.GetDataItems( memberValues, reverseOrder );
      }
      // Set the query parameters to start at a precise group or item.
      else if( queryParameters.Jump != null )
      {
        JumpRequest jumpRequest = queryParameters.Jump;
        JumpStartPosition startPosition = jumpRequest.StartPosition;
        IEnumerable<object> jumpValues = ListDataSourceProvider.GetJumpValues( jumpRequest.Values );
        bool includeStartingItem = ( startPosition == JumpStartPosition.Before );

        enumerable = index.GetDataItems( jumpValues, reverseOrder, !includeStartingItem );
      }
      // Set the query parameters to start on the first or last item.
      else
      {
        enumerable = index.GetDataItems( reverseOrder );
      }

      return enumerable;
    }

    private IEnumerable<long> GetGroupCount(
      JumpRequest jumpRequest,
      FilterGroupRequest filterGroupRequest,
      ListDataItemIndex index,
      int levelCount,
      bool reverseOrder )
    {
      if( index == null )
        throw new ArgumentNullException( "index" );

      IEnumerable<int> groupCount;

      if( ( jumpRequest != null ) && ( filterGroupRequest != null ) )
      {
        JumpStartPosition startPosition = jumpRequest.StartPosition;
        IEnumerable<object> jumpValues = ListDataSourceProvider.GetJumpValues( jumpRequest.Values );
        bool includeStartingItem = ( startPosition == JumpStartPosition.Before );
        IEnumerable<object> groupValues = ListDataSourceProvider.GetFilterGroupValues( filterGroupRequest.Values );

        groupCount = index.GetGroupCount(
                       levelCount,
                       groupValues,
                       jumpValues,
                       reverseOrder,
                       !includeStartingItem );
      }
      // Count every group from a starting position.
      else if( jumpRequest != null )
      {
        JumpStartPosition startPosition = jumpRequest.StartPosition;
        IEnumerable<object> jumpValues = ListDataSourceProvider.GetJumpValues( jumpRequest.Values );
        bool includeStartingItem = ( startPosition == JumpStartPosition.Before );

        groupCount = index.GetGroupCount(
                       levelCount,
                       jumpValues,
                       reverseOrder,
                       !includeStartingItem );
      }
      // Count the children of a specific group.
      else if( filterGroupRequest != null )
      {
        IEnumerable<object> groupValues = ListDataSourceProvider.GetFilterGroupValues( filterGroupRequest.Values );

        groupCount = index.GetGroupCount( levelCount, groupValues );
      }
      // Count every group.
      else
      {
        groupCount = index.GetGroupCount( levelCount );
      }

      return ( from count in groupCount
               select Convert.ToInt64( count ) );
    }

    private ListDataItemIndex GetIndex( FilterRequest filterRequest )
    {
      Predicate<object> filter;
      FilterExpressionBase filterExpression;

      ListDataSourceProvider.GetFilter( filterRequest, out filter, out filterExpression );

      return this.GetIndex( null, null, filter, filterExpression, true );
    }

    private ListDataItemIndex GetIndex(
      SortRequest sortRequest,
      FilterRequest filterRequest,
      bool allowSubset,
      out bool reversedOrder )
    {
      reversedOrder = false;

      if( sortRequest == null )
        return this.GetIndex( filterRequest );

      // Retrieve the sort order.
      IList<SortDescription> sortOrder = sortRequest.SortDescriptions;
      IComparer comparer = new NullComparer( new DefaultComparer() );
      IEnumerable<IComparer> comparers = Enumerable.Repeat( comparer, sortOrder.Count );

      // Retrieve the filter.
      Predicate<object> filter;
      FilterExpressionBase filterExpression;
      ListDataSourceProvider.GetFilter( filterRequest, out filter, out filterExpression );

      // Get the appropriate index for the task.
      ListDataItemIndex index = this.GetIndex( sortOrder, comparers, filter, filterExpression, allowSubset );
      reversedOrder = ListDataSourceProvider.IsSortOrderReversed( index, sortOrder );

      return index;
    }

    private ListDataItemIndex GetIndex(
      IEnumerable<SortDescription> sortOrder,
      IEnumerable<IComparer> groupValueComparers,
      Predicate<object> filter,
      FilterExpressionBase filterExpression,
      bool allowSubset )
    {
      // Check if an existing index match the requirements.
      LinkedListNode<ListDataItemIndex> node = m_indexes.First;
      while( node != null )
      {
        ListDataItemIndex index = node.Value;
        ListDataItemIndexConfiguration configuration = index.Configuration;

        // Check out if the filtering applied on the index matches.
        if( ( configuration.Filter == filter ) && ( configuration.FilterExpression == filterExpression ) )
        {
          // Check out if the index can be use for the given sort order.
          if( ( sortOrder == null )
            || ( allowSubset && ListDataSourceProvider.IsSubsetSortOrder( index, sortOrder ) )
            || ( !allowSubset && ListDataSourceProvider.IsExactSortOrder( index, sortOrder ) ) )
          {
            // Move the selected index closer to the first index in order to find it quicker next time.
            if( node.Previous != null )
            {
              LinkedListNode<ListDataItemIndex> previousIndex = node.Previous;
              m_indexes.Remove( index );
              m_indexes.AddBefore( previousIndex, index );
            }

            return index;
          }
        }

        // Check out the next index;
        node = node.Next;
      }

      // Free up old indexes.
      while( ( m_indexes.Count >= ListDataSourceProvider.MaximumIndexCount ) && ( m_indexes.Count > 0 ) )
      {
        m_indexes.RemoveLast();
      }

      List<IComparer> newGroupValueComparers = new List<IComparer>();
      if( groupValueComparers != null )
      {
        newGroupValueComparers.AddRange( groupValueComparers );
      }

      List<SortDescription> newSortOrder = new List<SortDescription>();
      if( sortOrder != null )
      {
        newSortOrder.AddRange( sortOrder );
      }

      // Make sure the primary key fields are included in the sort.
      if( ( allowSubset ) || ( newSortOrder.Count <= 0 ) )
      {
        foreach( SortDescription pk in this.PrimaryKeyInfo )
        {
          // It is useless to include the same field twice.
          if( newSortOrder.Select( ( item ) => item.PropertyName ).Contains( pk.PropertyName ) )
            continue;

          newSortOrder.Add( pk );
          newGroupValueComparers.Add( new NullComparer( new DefaultComparer() ) );
        }
      }

      // Create a new index that will fit the given configuration.
      ListDataItemIndexConfiguration newConfiguration = new ListDataItemIndexConfiguration(
                                                          newSortOrder,
                                                          newGroupValueComparers,
                                                          filter,
                                                          filterExpression,
                                                          m_collection.ElementType,
                                                          this.GetElementMemberType );
      ListDataItemIndex newIndex = new ListDataItemIndex( m_collection, newConfiguration );
      m_indexes.AddFirst( newIndex );

      return newIndex;
    }

    private static IEnumerable<RawDataItem> Skip(
      IEnumerable<RawDataItem> dataItems,
      SkipRequest request )
    {
      if( request != null )
      {
        long skipCount = request.Count;
        while( skipCount > 0 )
        {
          int count = ( skipCount > int.MaxValue )
                        ? int.MaxValue
                        : Convert.ToInt32( skipCount );
          dataItems = dataItems.Skip( count );
          skipCount -= count;
        }
      }

      return dataItems;
    }

    private static IEnumerable<RawDataItem> Take(
      IEnumerable<RawDataItem> dataItems,
      TakeRequest request )
    {
      if( request != null )
      {
        dataItems = dataItems.Take( request.Count );
      }

      return dataItems;
    }

    private static void GetFilter(
      FilterRequest request,
      out Predicate<object> filter,
      out FilterExpressionBase filterExpression )
    {
      if( request != null )
      {
        filter = request.Filter;
        filterExpression = request.Expression;
      }
      else
      {
        filter = null;
        filterExpression = null;
      }
    }

    private static bool IsExactSortOrder(
      ListDataItemIndex index,
      IEnumerable<SortDescription> sortOrder )
    {
      bool reversed;
      return ListDataSourceProvider.IsExactSortOrder( index, sortOrder, out reversed );
    }

    private static bool IsSubsetSortOrder(
      ListDataItemIndex index,
      IEnumerable<SortDescription> sortOrder )
    {
      bool reversed;
      return ListDataSourceProvider.IsSubsetSortOrder( index, sortOrder, out reversed );
    }

    private static bool IsExactSortOrder(
      ListDataItemIndex index,
      IEnumerable<SortDescription> sortOrder,
      out bool reversed )
    {
      reversed = false;

      return ( ListDataSourceProvider.IsSubsetSortOrder( index, sortOrder, out reversed ) )
          && ( index.Configuration.SortOrder.Count == sortOrder.Count() );
    }

    private static bool IsSubsetSortOrder(
      ListDataItemIndex index,
      IEnumerable<SortDescription> sortOrder,
      out bool reversed )
    {
      reversed = false;

      IList<SortDescription> indexSortOrder = index.Configuration.SortOrder;
      if( indexSortOrder.Count <= 0 )
        return !sortOrder.Any();

      Nullable<bool> isReversed = null;
      int i = 0;

      foreach( SortDescription sort in sortOrder )
      {
        if( i >= indexSortOrder.Count )
          return false;

        SortDescription indexSort = indexSortOrder[ i ];
        if( sort.PropertyName != indexSort.PropertyName )
          return false;

        bool oppositeOrder = ( sort.Direction != indexSort.Direction );
        if( isReversed.HasValue )
        {
          // The index isn't sorted in appropriate order.
          if( oppositeOrder != isReversed.Value )
            return false;
        }
        else
        {
          isReversed = oppositeOrder;
        }

        i++;
      }

      reversed = isReversed.GetValueOrDefault( false );
      return true;
    }

    private static bool IsSortOrderReversed(
      ListDataItemIndex index,
      IEnumerable<SortDescription> sortOrder )
    {
      bool reversed;
      ListDataSourceProvider.IsSubsetSortOrder( index, sortOrder, out reversed );

      return reversed;
    }

    private static IEnumerable<object> GetMemberValues(
      RawDataItem dataItem,
      IEnumerable<SortDescription> sortOrder )
    {
      return ( from sort in sortOrder
               select dataItem.GetDataMemberValue( sort.PropertyName ) );
    }

    private static IEnumerable<object> GetJumpValues( IEnumerable<JumpValue> values )
    {
      foreach( JumpValue jumpValue in values )
      {
        yield return jumpValue.Value;
      }
    }

    private static StatResult GetStatResult(
      StatFunction statFunction,
      IEnumerable<RawDataItem> dataItems,
      long count )
    {
      IEnumerator<RawDataItem> enumerator = dataItems.GetEnumerator();

      try
      {
        for( long i = 0; ( enumerator.MoveNext() ) && ( i < count ); i++ )
        {
          RawDataItem dataItem = enumerator.Current;

          statFunction.Accumulate( ( from spn in statFunction.GetSourcePropertyNames()
                                     select dataItem.GetDataMemberValue( spn ) ).ToArray() );
        }

        return statFunction.GetResult();
      }
      catch( Exception e )
      {
        return new StatResult( e );
      }
    }

    private static IEnumerable<object> GetFilterGroupValues( IEnumerable<FilterGroupValue> values )
    {
      foreach( FilterGroupValue groupValue in values )
      {
        yield return groupValue.Value;
      }
    }

    private bool TryGetItem( object userObject, out RawDataItem dataItem )
    {
      dataItem = null;

      // Save us the time to look for the user object if it isn't of the expected type.
      if( ( userObject == null ) ||
          ( this.ElementType.IsAssignableFrom( userObject.GetType() ) ) )
      {
        dataItem = m_collection.FirstOrDefault( ( item ) => item.Data == userObject );
      }

      return ( dataItem != null );
    }

    private void ClearIndexes()
    {
      // Clear all indexes to start from scratch on the next query.
      m_indexes.Clear();
    }

    private void AddDataItems( IEnumerable<RawDataItem> dataItems )
    {
      Action<ListDataItemIndex, RawDataItem> action =
        ( index, dataItem ) => index.Add( dataItem );

      this.ManageDataItems( dataItems, action );
    }

    private void RemoveDataItems( IEnumerable<RawDataItem> dataItems )
    {
      Action<ListDataItemIndex, RawDataItem> action =
        ( index, dataItem ) => index.Remove( dataItem );

      this.ManageDataItems( dataItems, action );
    }

    private void ManageDataItems(
      IEnumerable<RawDataItem> dataItems,
      Action<ListDataItemIndex, RawDataItem> action )
    {
      if( dataItems == null || action == null )
        return;

      foreach( ListDataItemIndex index in m_indexes )
      {
        index.ClearStatResults();

        foreach( RawDataItem dataItem in dataItems )
        {
          action.Invoke( index, dataItem );
        }
      }
    }

    private void OnItemsAdded( IEnumerable<RawDataItem> dataItems )
    {
      this.AddDataItems( dataItems );

      DataSourceChangedEventArgs eventArgs = new DataSourceChangedEventArgs(
                                                DataSourceChangedAction.Add,
                                                dataItems.Cast<object>(),
                                                null );
      this.OnDataSourceChanged( eventArgs );
    }

    private void OnItemsRemoved( IEnumerable<RawDataItem> dataItems )
    {
      this.RemoveDataItems( dataItems );

      DataSourceChangedEventArgs eventArgs = new DataSourceChangedEventArgs(
                                                DataSourceChangedAction.Remove,
                                                null,
                                                dataItems.Cast<object>() );
      this.OnDataSourceChanged( eventArgs );
    }

    private void OnItemsReplaced(
      IEnumerable<RawDataItem> newDataItems,
      IEnumerable<RawDataItem> oldDataItems )
    {
      this.RemoveDataItems( oldDataItems );
      this.AddDataItems( newDataItems );

      DataSourceChangedEventArgs eventArgs = new DataSourceChangedEventArgs(
                                                DataSourceChangedAction.Replace,
                                                newDataItems.Cast<object>(),
                                                oldDataItems.Cast<object>() );
      this.OnDataSourceChanged( eventArgs );
    }

    private void OnItemsReset()
    {
      // Clear all indexes to start from scratch on the next query.
      this.ClearIndexes();

      DataSourceChangedEventArgs eventArgs = new DataSourceChangedEventArgs( DataSourceChangedAction.Reset );
      this.OnDataSourceChanged( eventArgs );
    }

    private void OnItemsChanged( IEnumerable<ItemChangedDescription> itemsChanged )
    {
      if( ( itemsChanged == null ) || ( !itemsChanged.Any() ) )
        return;

      foreach( ItemChangedDescription itemChanged in itemsChanged )
      {
        // Retrieve the targeted item.
        RawDataItem dataItem = ( RawDataItem )itemChanged.Item;

        // Refresh the indexes since the targeted item may have changed.
        RawDataItem[] dataItems = new RawDataItem[] { dataItem };

        this.RemoveDataItems( dataItems );
        this.AddDataItems( dataItems );
      }

      DataSourceChangedEventArgs eventArgs = new DataSourceChangedEventArgs( itemsChanged );
      this.OnDataSourceChanged( eventArgs );
    }

    private void OnNotifyCollectionChanged( object sender, NotifyCollectionChangedEventArgs e )
    {
      if( e.Action == NotifyCollectionChangedAction.Add )
      {
        if( e.NewItems != null )
        {
          this.OnItemsAdded( e.NewItems.Cast<RawDataItem>() );
        }
      }
      else if( e.Action == NotifyCollectionChangedAction.Remove )
      {
        if( e.OldItems.Count > 0 )
        {
          this.OnItemsRemoved( e.OldItems.Cast<RawDataItem>() );
        }
      }
      else if( e.Action == NotifyCollectionChangedAction.Replace )
      {
        if( ( e.NewItems.Count > 0 ) && ( e.NewItems.Count == e.OldItems.Count ) )
        {
          this.OnItemsReplaced(
            e.NewItems.Cast<RawDataItem>(),
            e.OldItems.Cast<RawDataItem>() );
        }
      }
      else if( e.Action == NotifyCollectionChangedAction.Reset )
      {
        this.OnItemsReset();
      }
      else
      {
        throw new InvalidOperationException( "The received collection-changed action is not supported." );
      }
    }

    private void OnNotifyItemChanged( object sender, ItemChangedEventArgs e )
    {
      this.OnItemsChanged( e.ItemsChanged );
    }

    #region Private Fields

    private IEnumerable m_originalDataSource; //null
    private ListDataItemCollection m_collection; //null
    private LinkedList<ListDataItemIndex> m_indexes = new LinkedList<ListDataItemIndex>();

    #endregion

    #region Private DefaultComparer Nested Type

    private class DefaultComparer : IComparer
    {
      public int Compare( object x, object y )
      {
        IComparable firstValue = ( IComparable )x;
        IComparable secondValue = ( IComparable )y;

        if( ( firstValue != null ) && ( secondValue != null ) )
        {
          return firstValue.CompareTo( secondValue );
        }
        else if( firstValue != null )
        {
          return 1;
        }
        else if( secondValue != null )
        {
          return -1;
        }
        else
        {
          return 0;
        }
      }
    }

    #endregion

    #region Private NullComparer Nested Type

    private class NullComparer : IComparer
    {
      internal NullComparer( IComparer comparer )
      {
        if( comparer == null )
          throw new ArgumentNullException( "comparer" );

        m_comparer = comparer;
      }

      public int Compare( object x, object y )
      {
        if( ( x != null ) && ( y != null ) )
          return m_comparer.Compare( x, y );

        if( x != null )
          return 1;

        if( y != null )
          return -1;

        return 0;
      }

      private IComparer m_comparer;
    }

    #endregion
  }
}
